package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-28
 */

/**
 * 将一个链表m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。
 * 例如：
 * 给出的链表为 1→2→3→4→5→NULL, m=2,n=4,
 * 返回 1→4→3→2→5→NULL.
 * 注意：
 * 给出的 m,n 满足以下条件：
 * 1≤m≤n≤链表长度
 */
public class NC21 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode dim = new ListNode();
        dim.next = head;
        ListNode pre = dim;

        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode left = pre.next;

        ListNode right = pre;
        for (int i = 0; i < n - m + 1; i++) {
            right = right.next;
        }
        ListNode after = right.next;
        pre.next = null;
        right.next = null;
        pre.next = reverse(left);
        left.next = after;

        return dim.next;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
